The present application relates generally to an improved data processing apparatus and method and more specifically to mechanisms for providing high bandwidth decompression of variable length encoded data streams.
Lossless data compression is a class of data compression algorithms that allow the exact original data to be reconstructed from the compressed data. The term “lossless” is in contrast to lossy data compression techniques which only allow an approximation of the original data to be reconstructed in exchange for better compression rates. Lossless data compression is used in many different types of applications including the ZIP compression format, GZIP compression in Unix operating system based computing systems, and the like.
One type of lossless data compression is the DEFLATE data compression algorithm described in U.S. Pat. No. 5,051,745. The DEFLATE data compression algorithm makes use of a combination of the Lempel-Ziv LZ77 compression algorithm and Huffman coding. LZ77 compression is a sliding window compression technique in which, for a range (or window) of data, literal bytes of strings that have not yet been detected as duplicated are stored and when a duplicate string is detected within the range (or window), a pointer to the previously stored literal bytes is stored instead. The pointer comprises a length and a backward distance within the range (or window). Huffman encoding is then applied to the literal bytes and pointers in the LZ77 algorithm. Huffman encoding provides the ability to encode literal bytes and pointers using variable length encoding. More information regarding the DEFLATE data compression algorithm may be found in Deutsch, “DEFLATE Compressed Data Format Specification,” version 1.3, Network Working Group RFC 1951, May 1996.